The present invention relates to a method and apparatus for performing the floating point arithmetic operation of dividing in a data processing system. More particularly, the invention relates to an apparatus for implementing the method of 2-bit non-restoring division through a number of iterations, to produce a quotient from a floating point division circuit, and wherein the divide algorithm uses multiples of the divisor during these iterations. The present invention is specifically related to the selection of the particular multipliers to be used during each iteration of the divide operation.
The use of floating point arithmetic operations in a data processing system has been a common practice practically since the inception of computer technology. The development of floating point arithmetic hardware has taken many forms, usually with the objectives of simplifying the hardware construction, or enhancing the speed of the arithmetic processing operation. The four arithmetic operations of add, subtract, multiply and divide have usually been accomplished by using specialized subsets of processes involving addition and subtraction. For example, multiplication operations have in many cases been performed by repeated addition processes, and division has been accomplished by a process of repeated subtraction. The efforts made to speed up these processing operations have focused on enhancements and simplifications of hardware circuit design, particularly the adder circuit, which ultimately limits the maximum processing speed of all arithmetic operations. In the case of division, efforts have been made to increase the speed of operation by calculating partial quotients, or by simultaneously predicting multiple quotient bits, to reduce the number of addition or subtraction iterations required for the divide calculation.
Unfortunately, any arithmetic circuit utilizing an adder for carrying out an addition or subtraction inevitably involves the generation of carry bits which are propagated from least significant bit positions to more significant bit positions, and can in fact be propagated throughout all bit positions during an arithmetic operation. This has the affect of extending the processing time required for completing a calculation, and various design efforts have been made to deal with this problem. For example, U.S. Pat. No. 4,754,422, issued June 28, 1988, discloses a dividing apparatus utilizing three carry-save adders in an effort to produce a plurality of quotient bits during each iteration or cycle of arithmetic operation. U.S. Pat. No. 3,621,218, issued Nov. 16, 1971, discloses a high-speed divider utilizing a single carry-save adder for producing a plurality of quotient bits during each iteration of the arithmetic operation, and a plurality of registers for holding a sequence of partial quotients used in the operation.
IBM Technical Disclosure Bulletin, Volume 14, No. 11, April 1972 (pages 3279-3281) discloses a divider for producing two quotient bits per iteration, utilizing two carry-save adders and certain multiples of the divisor to speed up the operation.
An American National Standard has been developed, known as "IEEE Standard For Binary Floating Point Arithmetic", ANSI/IEEE Standard No. 754-1985. This standard sets forth the definitions, formats, and rules for performing certain floating point operations, including rules for dealing with the treatment of the results of floating point arithmetic operations. Among these rules, the standard requires the setting of a flag called "inexact result" if the result of a floating point arithmetic operation is not equal to the result that would have been produced if the calculation had been made to infinite precision. The standard also defines several different rules for performing rounding of arithmetic results when necessary.
The design of floating point arithmetic circuits and algorithms is strongly influenced by the provisions of ANSI/IEEE Standard No. 754-1985. It is desirable to design such circuits and algorithms to produce results which comply with all of the provisions of this standard, under all conditions of operation. For example IBM Technical Disclosure Bulletin, Vol. 30, No. 7, December 1987 (pages 276-278) discloses a method for producing an exact remainder, as defined in the standard, wherein the method is independent of the size of the argument. However, the paper does not specifically deal with the detection of an exact or inexact result, and therefore does not entirely respond to the requirement of the IEEE standard.
U.S. Pat. No. 3,852,581, issued Dec. 3, 1974, discloses a method and apparatus for performing a non-restoring division algorithm wherein two quotient bits are generated simultaneously during each addition cycle. A multiple of the divisor to be subtracted from four times the remainder for the succeeding cycle is selected concurrently with the remainder developed as the result of subtraction. A table and decoder are used to examine the magnitudes of the remainder in the divisor to predict this multiplication factor which may also be developed tentatively into the two bit quotient. A correction may be made to the tentative quotient as a result of the adder operation, the corrected quotient being entered into the quotient register. The patent does not disclose a solution to the problem of dealing with the ultimate remainder, detecting whether a result is exact or inexact, or rounding the final quotient.
It is a principal object of the present invention to provide an apparatus for floating point divide operations, wholly in conformance with ANSI/IEEE Standard No. 754-1985.
It is a further object of the present invention to provide an apparatus for performing floating point division operations wherein the quotient result may be properly rounded in accordance with ANSI/IEEE Standard No. 754-1985, and wherein the "inexact result" condition is properly indicated in conformance with the standard.
It is a further object of the present invention to provide an apparatus for holding multipliers which, when applied to divisors, accurately produces a quotient and remainder result which conforms to the standard.